class BIT:
def __init__(self, n):
self.n = n
self.bit = [0]*(self.n+1)
def init(self, init_val):
for i, v in enumerate(init_val):
self.add(i, v)
def add(self, i, x):
i += 1 while i <= self.n:
self.bit[i] += x
i += (i & -i)
def sum(self, i, j):
return self._sum(j) - self._sum(i)
def _sum(self, i):
res = 0
while i > 0:
res += self.bit[i]
i -= i & (-i)
return res
def lower_bound(self, x):
s = 0
pos = 0
depth = self.n.bit_length()
v = 1 << depth
for i in range(depth, -1, -1):
k = pos + v
if k <= self.n and s + self.bit[k] < x:
s += self.bit[k]
pos += v
v >>= 1
return pos
def __str__(self): arr = [self.sum(i,i+1) for i in range(self.n)]
return str(arr)
n = int(input())
A = list(map(int, input().split()))
A = [a-1 for a in A]
A = [min(a, n-1) for a in A]
bit = BIT(n+5)
B = [[] for i in range(n)]
for i, a in enumerate(A):
bit.add(i, 1)
B[a].append(i)
ans = 0
for i, a in enumerate(A):
ans += bit.sum(0, a+1)
for j in B[i]:
bit.add(j, -1)
for i, a in enumerate(A):
if a >= i:
ans -= 1
ans //= 2
print(ans)
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define int long long
#define ull unsigned long long
#define lowbit(i) ((i)&(-i))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 200;
int qpow(int a, int n) {
int ans = 1;
while (n) {
if (n & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
n >>= 1;
}
return ans;
}
//int a[N];
class BIT{
public:
vector<int> c;
int sz;
BIT(int n):c(n+1){sz=n;}
void add(int pos,int k);
int query(int i);
};
void BIT::add(long long pos, long long k) {
while(pos<=sz){
c[pos]+=k;
pos+=lowbit(pos);
}
}
int BIT::query(long long i) {
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int a[N];
signed main() {
IOS
int n;
cin>>n;
BIT bit(n+1);
vector<vector<int>> g(n+1,vector<int>());
for(int i=1;i<=n;i++)
{
cin>>a[i];
g[min(a[i],n)].push_back(i);
bit.add(i,1);
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=bit.query(min(a[i],n));
for(auto j:g[i])
{
bit.add(j,-1);
}
// cout<<ans<<endl;
}
for(int i=1;i<=n;i++)
{
if(a[i]>=i)ans--;
}
cout<<ans/2<<endl;
return 0;
}545B - Equidistant String | 1244C - The Football Season |
1696B - NIT Destroys the Universe | 1674A - Number Transformation |
1244E - Minimizing Difference | 1688A - Cirno's Perfect Bitmasks Classroom |
219A - k-String | 952A - Quirky Quantifiers |
451B - Sort the Array | 1505H - L BREAK into program |
171E - MYSTERIOUS LANGUAGE | 630D - Hexagons |
1690D - Black and White Stripe | 1688D - The Enchanted Forest |
1674C - Infinite Replacement | 712A - Memory and Crow |
1676C - Most Similar Words | 1681A - Game with Cards |
151C - Win or Freeze | 1585A - Life of a Flower |
1662A - Organizing SWERC | 466C - Number of Ways |
1146A - Love "A" | 1618D - Array and Operations |
1255A - Changing Volume | 1710C - XOR Triangle |
415C - Mashmokh and Numbers | 8A - Train and Peter |
591A - Wizards' Duel | 1703G - Good Key Bad Key |